This invention relates to a method and apparatus for planning networks and, in particular, telephone facilities networks.
Telephone facilities networks typically contain a large embedded, physical network (wire, cable, fiber, etc.) whose links (communication paths between nodes or central offices) are required to be changed over time to accommodate changes in demand. In order to meet demand changes in a suitable time frame, the owners of these networks have developed design plans which account for present and anticipated demand and which schedule changes to the network facilities (i.e., the addition or deletion of links) to occur at set times (usually during a specific quarter of a specific year). Furthermore, these plans are continually updated or revised also at specified intervals of time (usually quarterly).
In developing and updating a network facilities design plan, it is important that the plan provide for changes in the physical network to accommodate addition and/or deletion of links in a cost-effective, desirable and predictable way. The design plan must also take into account a myriad of diverse concerns applicable to the system. Thus, demand patterns, technology evolution and changes, economics, market conditions and government regulations are just some of the conditions or constraints which have to be considered.
Use of general methods to develop a design plan for network facilities by attempting to model the constraints involved in the context of an optimization algorithm have not proved entirely successful. These methodologies quickly grow beyond manageable proportions even with simplified models, due to the complexity of the constraints and the large size of the networks. Furthermore, deriving stable solutions with an algorithmic approach becomes even more difficult.
The general methods referred to above are usually classified as weak methods and their inability to effectively develop a plan and updates for telephone facilities networks stems in part from their entirely general nature which divorces their solution strategy from any component of the facilities network domain information. Typical of the weak methods in use today are the following: generate and test; hill climbing; and breadth first and best first search.
The common procedure in these weak methods is to create an arbitrary solution to a problem, determine its goodness, and then either stop or proceed to determine a next solution. By themselves, these methods are in-effectual in determining a solution where the problem involves complex constraints.
Thus, creating an arbitrary solution may in fact be as difficult as finding the desired solution. Furthermore, to establish a measure of goodness for a solution, one needs to have a clearly defined objective function. For the complex problem of telephone network facilities planning, it is hard to determine a computable objective function. If the objective function is qualitative, it is difficult to find an algorithmic solution to optimize it. It also becomes very difficult to find a next or subsequent solution based on the previous solution in a way that ensures successive movement towards the desired solution. Sometimes it is possible to model a highly simplified version of a complex network in such a way as to establish a computable objective function, but even then, the optimization itself remains highly intractable and the solution must be found approximately using numerical methods.
An important aspect of these weak methods is that at any given point in the process, the solution does not represent the desired solution (until the final step). Thus it is imperative that the iterative process continue until an acceptable solution can be found. This implies that it must be possible to know how good a solution is and how to improve it. Further, it frequently implies that a complete optimization type algorithm must be implemented to determine the best solution, since there is no prior information about the desired solution. Accordingly, the weak methods have not been successful in developing solutions to telephone facilities planning.
It is, therefore, an object of the present invention to provide a method and apparatus for developing a plan for the facilities of a telephone network which does not suffer from the above disadvantages of weak methods.
It is a further object of the present invention to provide a method and apparatus for developing a plan for changing the links of a telephone network which is deterministic, predictable and does not require exhaustive optimization.